算法复杂度

同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。

空间复杂度

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做 $S (n) = O (f (n))$ 。

时间复杂度(Time Complexity)是对一个算法在运行过程中代码语句执行次数的量度，记做 $T (n) = O (f (n))$ 。

代码 1

python

for i in range(5):
    print(i)

代码 2

python

n = int(input())
for i in range(n - 1):
    print(i)

上述两段代码，程序执行次数分别是 5 次和 n-1 次。

变量使用数量分别是 1 个和 2 个。

时间复杂度分别记为 $T (n) = 5$ 和 $T (n) = n - 1$ 。

空间复杂度分别记为 $S (n) = 1$ 和 $S (n) = 2$

$O (T (n))$ 会将所有系数和低次项去除，只保留高次项，如果是常数，则记为 $O (1)$ 。

例如， $O (3 n^{3} + 2 n^{2} + 1) = O (n^{3})$

例如， $O (100) = O (1)$

	代码 1	代码 2
时间复杂度	$O (1)$	$O (n)$
空间复杂度	$O (1)$	$O (1)$

优化时间复杂度

可以看到，不同时间复杂度对于程序运行的速度影响非常大，所以选择合适的算法，提升程序运行速度，优化时间复杂度是非常有必要的。

有的时候，要提升程序运行速度，可能需要使用更多的空间，在降低时间复杂度的同时，会增加空间复杂度，这就是以空间换时间。

但有的时候，为了节约存储空间，在降低空间复杂度的同时，会增加时间复杂度，这就是以时间换空间。

所以两者之间的选择，要根据实际情况去判断。